import java.util.Scanner;

// 定义链表节点类
class Node {
    int data; // 存储节点的数据
    Node next; // 存储指向下一个节点的引用

    // 节点的构造函数，用于初始化节点的数据
    Node(int data) {
        this.data = data; // 将传入的数据赋值给节点的数据域
        this.next = null; // 新节点的next默认指向null
    }
}

public class LinkedListSequenceList {
    private Node head; // 用于存储链表的头节点

    // 链表的构造函数，初始化链表为空（头节点为null）
    public LinkedListSequenceList() {
        this.head = null;
    }

    // 1. 创建链表
    public void createList(int[] elements) {
        head = null; // 先将头节点设为null，准备构建新链表
        Node current = null; // 用于遍历和构建链表的当前节点引用，初始为null

        // 遍历输入的元素数组
        for (int element : elements) {
            Node newNode = new Node(element); // 创建一个新的节点，存储当前元素

            // 如果链表为空，将新节点设为头节点，并更新当前节点
            if (head == null) {
                head = newNode;
                current = head;
            } else {
                // 如果链表不为空，将新节点连接到当前节点的后面，并更新当前节点
                current.next = newNode;
                current = newNode;
            }
        }
        sort(); // 对创建好的链表进行排序
        System.out.println("创建成功！当前链表所有元素：" + this); // 输出创建成功的提示和链表内容
    }

    // 2. 插入元素到指定位置
    public void insert(int position, int element) {
        // 检查插入位置是否小于1，小于1则位置不合法
        if (position < 1) {
            System.out.println("插入位置不合法！");
            return; // 位置不合法，直接返回，不进行插入操作
        }

        Node newNode = new Node(element); // 创建要插入的新节点

        // 如果插入位置是1，即要插入到链表头部
        if (position == 1) {
            newNode.next = head; // 新节点的next指向原头节点
            head = newNode; // 更新头节点为新节点
        } else {
            Node current = head; // 从链表头节点开始遍历
            int count = 1; // 用于记录当前遍历到的位置

            // 遍历链表，找到插入位置的前一个节点
            while (current != null && count < position - 1) {
                current = current.next; // 移动到下一个节点
                count++; // 位置计数加1
            }

            // 如果遍历完链表都没找到合适位置（即插入位置超过链表长度），则位置不合法
            if (current == null) {
                System.out.println("插入位置不合法！");
                return; // 位置不合法，直接返回，不进行插入操作
            }

            // 将新节点插入到找到的位置
            newNode.next = current.next; // 新节点的next指向原位置的节点
            current.next = newNode; // 原位置前一个节点的next指向新节点
        }
        System.out.println("插入成功！！！当前链表所有元素：" + this); // 输出插入成功的提示和链表内容
    }

    // 3. 删除指定位置的元素
    public void delete(int position) {
        // 检查删除位置是否小于1，小于1则位置不合法
        if (position < 1) {
            System.out.println("删除位置不合法！");
            return; // 位置不合法，直接返回，不进行删除操作
        }

        // 如果要删除的是头节点
        if (position == 1) {
            head = head.next; // 头节点指向下一个节点，即删除原头节点
        } else {
            Node current = head; // 从链表头节点开始遍历
            int count = 1; // 用于记录当前遍历到的位置

            // 遍历链表，找到删除位置的前一个节点
            while (current != null && count < position - 1) {
                current = current.next; // 移动到下一个节点
                count++; // 位置计数加1
            }

            // 如果遍历完链表都没找到合适位置（即删除位置超过链表长度），则位置不合法
            if (current == null || current.next == null) {
                System.out.println("删除位置不合法！");
                return; // 位置不合法，直接返回，不进行删除操作
            }

            // 删除指定位置的节点
            current.next = current.next.next; // 将前一个节点的next指向要删除节点的下一个节点
        }
        System.out.println("删除成功！！！当前链表所有元素：" + this); // 输出删除成功的提示和链表内容
    }

    // 4. 顺序查找（线性查找）
    public int sequentialSearch(int key) {
        Node current = head; // 从链表头节点开始查找
        int position = 1; // 用于记录当前节点的位置，从1开始

        // 遍历链表
        while (current != null) {
            // 如果当前节点的数据等于要查找的关键字
            if (current.data == key) {
                return position; // 返回当前节点的位置
            }
            current = current.next; // 移动到下一个节点
            position++; // 位置计数加1
        }
        return -1; // 遍历完链表都没找到，返回-1表示未找到
    }

    // 5. 折半查找（二分查找，要求链表有序）
    public int binarySearch(int key) {
        // 将链表转换为数组进行二分查找
        int[] arr = linkedListToArray();

        int low = 0; // 二分查找的下界
        int high = arr.length - 1; // 二分查找的上界

        // 二分查找循环
        while (low <= high) {
            int mid = (low + high) / 2; // 计算中间位置

            // 如果中间位置的元素等于要查找的关键字
            if (arr[mid] == key) {
                return findPositionInLinkedList(key); // 在链表中找到该元素的实际位置并返回
            } else if (arr[mid] < key) { // 如果中间位置的元素小于关键字
                low = mid + 1; // 调整下界
            } else { // 如果中间位置的元素大于关键字
                high = mid - 1; // 调整上界
            }
        }
        return -1; // 未找到，返回-1
    }

    // 辅助方法：将链表转换为数组
    private int[] linkedListToArray() {
        int size = 0; // 用于记录链表的长度
        Node current = head; // 从链表头节点开始遍历

        // 计算链表长度
        while (current != null) {
            size++;
            current = current.next;
        }

        int[] arr = new int[size]; // 创建一个与链表长度相同的数组
        current = head; // 再次从链表头节点开始
        int index = 0; // 数组的索引

        // 将链表元素复制到数组中
        while (current != null) {
            arr[index] = current.data; // 将当前节点的数据存入数组
            index++; // 数组索引加1
            current = current.next; // 移动到下一个节点
        }
        return arr; // 返回转换后的数组
    }

    // 辅助方法：在链表中找到元素的位置
    private int findPositionInLinkedList(int key) {
        Node current = head; // 从链表头节点开始查找
        int position = 1; // 用于记录当前节点的位置，从1开始

        // 遍历链表
        while (current != null) {
            // 如果当前节点的数据等于要查找的关键字
            if (current.data == key) {
                return position; // 返回当前节点的位置
            }
            current = current.next; // 移动到下一个节点
            position++; // 位置计数加1
        }
        return -1; // 遍历完链表都没找到，返回-1表示未找到
    }

    // 6. 倒置链表
    public void reverse() {
        Node prev = null; // 用于记录当前节点的前一个节点，初始为null
        Node current = head; // 从链表头节点开始
        Node next = null; // 用于记录当前节点的下一个节点

        // 遍历链表，进行节点指针的反转
        while (current != null) {
            next = current.next; // 保存当前节点的下一个节点
            current.next = prev; // 将当前节点的next指向前一个节点
            prev = current; // 更新前一个节点为当前节点
            current = next; // 更新当前节点为原来的下一个节点
        }
        head = prev; // 遍历完后，新的头节点是原链表的最后一个节点
        System.out.println("倒置成功！当前链表所有元素：" + this); // 输出倒置成功的提示和链表内容
    }

    // 7. 输出链表内容（重写toString方法）
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(); // 创建一个StringBuilder用于拼接链表元素
        Node current = head; // 从链表头节点开始

        // 遍历链表
        while (current != null) {
            sb.append(current.data); // 将当前节点的数据添加到StringBuilder中

            // 如果不是最后一个节点，添加两个空格作为分隔
            if (current.next != null) {
                sb.append("  ");
            }
            current = current.next; // 移动到下一个节点
        }
        return sb.toString(); // 返回拼接好的字符串
    }

    // 8. 清空链表
    public void clear() {
        head = null; // 将头节点设为null，即清空链表
        System.out.println("链表已清空！"); // 输出清空成功的提示
    }

    // 9. 排序链表（使用简单的冒泡排序）
    public void sort() {
        // 如果链表为空，直接返回
        if (head == null) {
            return;
        }

        Node current = head; // 从链表头节点开始
        int swapped; // 用于标记在一次遍历中是否有节点交换

        do {
            swapped = 0; // 每次遍历开始时，设为未交换
            current = head; // 从链表头节点开始

            // 遍历链表，比较相邻节点
            while (current.next != null) {
                // 如果当前节点的数据大于下一个节点的数据
                if (current.data > current.next.data) {
                    int temp = current.data; // 交换两个节点的数据
                    current.data = current.next.data;
                    current.next.data = temp;
                    swapped = 1; // 标记有节点交换
                }
                current = current.next; // 移动到下一个节点
            }
        } while (swapped == 1); // 如果有节点交换，继续下一轮遍历

        System.out.println("排序成功！！！当前链表所有元素：" + this); // 输出排序成功的提示和链表内容
    }

    // 主程序入口
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建Scanner对象用于接收用户输入
        LinkedListSequenceList list = new LinkedListSequenceList(); // 创建链表对象
        System.out.println("\n1. 创建\n2. 插入\n3. 删除\n4. 顺序查找\n5. 折半查找\n6. 倒置\n7. 输出\n8. 清空\n9. 排序\n0. 返回");
        while (true) {
            // 打印操作菜单
            System.out.print("请选择你的操作：");
            int choice = scanner.nextInt(); // 读取用户的选择
            // 根据用户选择执行相应操作
            switch (choice) {
                case 1:
                    System.out.print("请输入要创建的链表长度：");
                    int len = scanner.nextInt(); // 读取要创建的链表长度

                    System.out.print("请输入" + len + "个数（空格隔开，可无序输入）：");
                    int[] elements = new int[len]; // 创建用于存储输入元素的数组

                    // 读取用户输入的元素
                    for (int i = 0; i < len; i++) {
                        elements[i] = scanner.nextInt();
                    }
                    list.createList(elements); // 创建链表
                    break;
                case 2:
                    // 检查链表是否为空，为空则提示先创建链表
                    if (list.head == null) {
                        System.out.println("请先创建链表！");
                        break;
                    }
                    System.out.print("请输入要插入的位置（从1开始）及元素：");
                    int pos = scanner.nextInt(); // 读取插入位置
                    int elem = scanner.nextInt(); // 读取要插入的元素
                    list.insert(pos, elem); // 插入元素
                    break;
                case 3:
                    // 检查链表是否为空，为空则提示先创建链表
                    if (list.head == null) {
                        System.out.println("请先创建链表！");
                        break;
                    }
                    System.out.print("请输入要删除的位置（从1开始）：");
                    int delPos = scanner.nextInt(); // 读取删除位置
                    list.delete(delPos); // 删除元素
                    break;
                case 4:
                    // 检查链表是否为空，为空则提示先创建链表
                    if (list.head == null) {
                        System.out.println("请先创建链表！");
                        break;
                    }
                    System.out.print("请输入要查找的元素：");
                    int seqKey = scanner.nextInt(); // 读取要查找的元素
                    int seqResult = list.sequentialSearch(seqKey); // 进行顺序查找

                    // 根据查找结果输出相应信息
                    if (seqResult != -1) {
                        System.out.println("元素 " + seqKey + " 位于第 " + seqResult + " 个位置");
                    } else {
                        System.out.println("未找到元素 " + seqKey);
                    }
                    break;
                case 5:
                    // 检查链表是否为空，为空则提示先创建链表
                    if (list.head == null) {
                        System.out.println("请先创建链表！");
                        break;
                    }
                    System.out.print("请输入要查找的元素：");
                    int binKey = scanner.nextInt(); // 读取要查找的元素
                    int binResult = list.binarySearch(binKey); // 进行折半查找

                    // 根据查找结果输出相应信息
                    if (binResult != -1) {
                        System.out.println("元素 " + binKey + " 位于第 " + binResult + " 个位置");
                    } else {
                        System.out.println("未找到元素 " + binKey);
                    }
                    break;
                case 6:
                    // 检查链表是否为空，为空则提示先创建链表
                    if (list.head == null) {
                        System.out.println("请先创建链表！");
                        break;
                    }
                    list.reverse(); // 倒置链表
                    break;
                case 7:
                    // 检查链表是否为空，为空则提示先创建链表
                    if (list.head == null) {
                        System.out.println("请先创建链表！");
                        break;
                    }
                    System.out.println("当前链表所有元素：" + list); // 输出链表内容
                    break;
                case 8:
                    // 检查链表是否为空，为空则提示先创建链表
                    if (list.head == null) {
                        System.out.println("请先创建链表！");
                        break;
                    }
                    list.clear(); // 清空链表
                    break;
                case 9:
                    // 检查链表是否为空，为空则提示先创建链表
                    if (list.head == null) {
                        System.out.println("请先创建链表！");
                        break;
                    }
                    list.sort(); // 对链表进行排序
                    break;
                case 0:
                    System.out.println("程序结束！"); // 输出程序结束提示
                    scanner.close(); // 关闭Scanner对象
                    return; // 结束程序
                default:
                    System.out.println("无效的选择，请重新输入！"); // 处理无效选择
            }
        }
    }
}